1. Field of Invention
The invention relates generally to databases and more specifically to query optimization.
2. Description of the Background Art
Computer databases have become a prevalent means for data storage and retrieval. A database user will commonly access the underlying data in a database using a Database Management System (“DBMS”). A user issues a query to the DBMS that conforms to a defined query language. This simplifies the user's interactions with the database by not requiring that the user know or understand the underlying structure of the physical database. Because of this, however, it is imperative that the DBMS execute the query in a manner which is most efficient for the underlying database.
Referring to FIG. 1, a DBMS 140 includes a compiler 164 that houses query optimizers such as a query optimizer 165. Query optimizer 165 determines the most efficient method to execute a query. When a client 110 writes an SQL query it is sent to DBMS 140, client 110 does not specify how the query should be executed by DBMS 140. Therefore, an effective design of the query optimizer 165 is critical to producing an efficient DBMS 140.
Query optimizer 165 analyzes the query and deter mines an access plan. This includes, for example, choosing the access method for each table accessed, choosing the order in which to perform a join operation on the tables, and choosing the join method to be used in each join operation. As there are typically many strategies for executing a given query using combinations of these operations, query optimizer 165 generates and evaluates a number of strategies from which to select the best one by way of an enumeration process (or “search space generation process”). A discussion of example optimizing strategies is provided in commonly-owned U.S. Pat. No. 7,184,998, issued Feb. 27, 2007, which is herein incorporated by reference in its entirety.
Conventionally, the query optimizer 165 uses a single optimization algorithm to determine strategies and form an access plan for optimizing a query. The same algorithm is used even though query optimizer 165 is executed on different platforms equipped with different system resources. Thus, if query optimizer 165 runs out of the available system resources during the optimization process, query optimizer 165 will fail to develop an access plan. This results in DBMS 140 executing a query without any optimization by a “brute force” approach or rejecting the query without executing the query. Thus, what is needed is an improved query optimizer 165 that can optimize a query using a query optimization algorithm that is selected from a plurality of available query optimization algorithms, where in an embodiment the selected algorithm is the one that is least expensive in light of the complexity of the query and the available system resources. What is also needed is query optimizer 165 that selects an algorithm that will create an access plan to optimize a query given the available system resources.
Accordingly, systems, methods and articles of manufacture are needed that allow query optimizer 165 to select a query optimization algorithm based on available system resources that can efficiently optimize a search performed by a query.